package Medir.java;

public class HeapSort
{
	int heapsize = 0;
	
	public void Exchange(float[] a, int i, int j)
	{
	float temp = a[i];
	a[i] = a[j];
	a[j] = temp;	
	}
public int Left(int i)
{
	return 2 * i;
}

public int Right(int i)
{
	return 2 * i +1;
}
public HeapSort(float[] a)
{
	BuildMaxHeap(a);
	
	for(int i = a.length-1; i >=2; i--)
	{
		Exchange(a, 1, i);
		heapsize = heapsize -1;
		MaxHeapify(a,1);
	}
}
	
public void BuildMaxHeap(float[] a)	
{
	heapsize = a.length-1;
	for(int i = (int)Math.floor(a.length / 2.0); i >=1; i--) MaxHeapify(a,i);
	
	
}
public void MaxHeapify(float[] a, int i)
{
	int l = Left(i);
	int r = Right(i);
	int largest = 0;
	if(l <= heapsize && a[l] > a[i] )largest = l;
	else largest = i;
	if(r <= heapsize&& a[r]> a[largest]) largest = r;
	if(largest != i)
	{
		Exchange(a, i, largest);
		MaxHeapify(a, largest);
	}

}
}


